// https://www.lintcode.com/problem/longest-substring-without-repeating-characters/description
// 384. 最长无重复字符的子串
// 给定一个字符串，请找出其中无重复字符的最长子字符串。

// 样例
// 例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。

// 对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。

// 挑战
// O(n) 时间



class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    
    // 个
    int lengthOfLongestSubstring(string &s) {
        map<char, int> record;
        int maxLen = 0;
        int tmpLen = 0;
        int j = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            char c = s[i];
            if (record.find(c) != record.end())
            {
                int idx = record[c];
                maxLen = max(maxLen, tmpLen);
                tmpLen = i - idx - 1;
                while (j <= idx)
                {
                    record.erase(s[j++]); //前面的要去掉。可以用一个j一直记录
                }
            }
            record[c] = i;
            tmpLen++;
        }
        maxLen = max(maxLen, tmpLen);
        return maxLen;
    }
    
// 法一：双指针+哈希
    // int lengthOfLongestSubstring(string &s) {
    //     if (s.empty())
    //         return 0;
    //     map<char, bool> rec;
    //     int len = s.length();
    //     int res = 1;
    //     for (int l = 0, r = 0; r < len; ++r)
    //     {
    //         while (rec[s[r]])
    //         {
    //             rec.erase(s[l++]);
    //         }
    //         rec[s[r]] = true;
    //         if (r - l + 1 > res)
    //             res = r - l + 1;
    //     }
    //     return res;
    // }
    

 // 如果数组不大，推荐用数组而不是哈希表存。因为哈希表的O(1)是平均O(1)
    int lengthOfLongestSubstring(string &s) {
        if (s.empty())
            return 0;
        bool rec[255];
        memset(rec, false, sizeof rec);
        int res = 1;
        for (int l = 0, r = 0; l < s.length(); ++l)
        {
            while (r < s.length() && !rec[s[r]])
            {
                rec[s[r]] = true;
                if (r - l + 1 > res)
                    res = r - l + 1;
                r++;
            }
            rec[s[l]] = false;
        }
        return res;
    }
    

    // 法二：单指针，哈希
    int lengthOfLongestSubstring(string &s) {
        if (s.empty())
            return 0;
        map<char, int> rec;
        int left = 0;
        int n = s.length();
        int res = 1;
        for (int i = 0; i < n; ++i)
        {
            // if (rec[s[i]] >= left)
            if (rec.find(s[i]) != rec.end() && rec[s[i]] >= left)
            {
                left = rec[s[i]] + 1;
            }
            rec[s[i]] = i;
            if (i - left + 1 > res)
                res = i - left + 1;
        }
        return res; 
    }
};
